CF147B Smile House

貌似 @DDF_Van 大佬的标程过不了 , 有些题解用的二分会多一个lognlog_n,那就补一发倍增题解吧。

Solution 1

dp[s][i][j]dp[s][i][j]表示走了不多于ss条边,iji \to j的最大边权(走不通为极小值)

如果有uvu \to v的一条边,那么dp[1][u][v]=wdp[1][u][v]=www为这条边的权值)

那么转移为:

dp[s][i][j]=max(dp[s1][i][k]+dp[1][j][k])dp[s][i][j]=max(dp[s-1][i][k]+dp[1][j][k])

显然,如果存在dp[k][i][i](ks)dp[k][i][i](k \le s) , 那么答案为kk

时间复杂度Θ(n4)\Theta(n^4) , 70分。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 300;
int n , m , x , y , z , w , Ans;
int dp[ MAXN + 5 ][ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
    memset( dp , 0xcf , sizeof( dp ) );

    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d %d %d",&x,&y,&z,&w);
        dp[ 1 ][ x ][ y ] = z;
        dp[ 1 ][ y ][ x ] = w;
    }
    for( int s = 2 ; s <= n ; s ++ ) {
        for( int k = 1 ; k <= n ; k ++ )
            for( int i = 1 ; i <= n ; i ++ ) {
                for( int j = 1 ; j <= n ; j ++ )
                    dp[ s ][ i ][ j ] = max( dp[ s ][ i ][ j ] , dp[ s - 1 ][ i ][ k ] + dp[ 1 ][ k ][ j ] );
                if( dp[ s ][ i ][ i ] > 0 ) {
                    Ans = s;
                    goto there;
                }
            }     
    } 
    there:;
    printf("%d",Ans);
    return 0;
}

Solution 2

我们有必要重新定义一下dpdp转移式,设dp[s][i][j]dp[s][i][j]表示走了不超过2s2^s条边,iji \to j的最大边权(走不通为极小值)。

那么转移为:

dp[s][i][j]=max(dp[s1][i][k]+dp[s1][k][j])dp[s][i][j]=max(dp[s-1][i][k]+dp[s-1][k][j])

我们可以用Θ(n3logn)\Theta(n^3log_n)预处理求出。


在我们计算答案时,我们用类似倍增爬树的方法。

先尝试走了不超过2s2^s条边从xx走到了yy的最小边权和 , ss从大到小枚举。

1.如果没有正环,说明答案大于2s2^s , 那么下一步增加2s12^{s-1}条边

转移时需用到上一次状态,用now[i][j]now[i][j]记录上一次尝试iji \to j的最长路径。

2.如果有正环,说明答案小于等于2s2^s,那么下一步尝试2s12^{s-1}条边


倍增时间复杂度为Θ(n3logn)\Theta(n^3log_n) , 总时间复杂度Θ(n3logn)\Theta(n^3log_n)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 300 , MAXK = 10;
int n , m , x , y , z , w , Ans;
int dp[ MAXK + 5 ][ MAXN + 5 ][ MAXN + 5 ];
int tmp[ MAXN + 5 ][ MAXN + 5 ] , now[ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
    memset( now , 0xcf , sizeof( now ) );
    memset( dp , 0xcf , sizeof( dp ) );

    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d %d %d",&x,&y,&z,&w);
        dp[ 0 ][ x ][ y ] = z;
        dp[ 0 ][ y ][ x ] = w;
    }
    for( int i = 1 ; i <= n ; i ++ )
        now[ i ][ i ] = 0 , dp[ 0 ][ i ][ i ] = 0;
    
    for( int s = 1 ; s <= MAXK ; s ++ )		//预处理
        for( int k = 1 ; k <= n ; k ++ )
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= n ; j ++ )
                    dp[ s ][ i ][ j ] = max( dp[ s ][ i ][ j ] , dp[ s - 1 ][ i ][ k ] + dp[ s - 1 ][ k ][ j ] );
    
    for( int s = MAXK ; s >= 0 ; s -- ) {
        memset( tmp , 0xcf , sizeof( tmp ) );

        for( int k = 1 ; k <= n ; k ++ )	//转移
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= n ; j ++ )
                    tmp[ i ][ j ] = max( tmp[ i ][ j ] , now[ i ][ k ] + dp[ s ][ k ][ j ] );

        bool f = 0;
        for( int i = 1 ; i <= n ; i ++ )
            if( tmp[ i ][ i ] > 0 ) {
                f = 1;
                break;
            }
        if( f ) continue;	//有正环
        else {				//无正环
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= n ; j ++ )
                    now[ i ][ j ] = tmp[ i ][ j ];
            Ans += 1 << s;
        }
    }
    printf("%d\n", Ans >= n ? 0 : Ans + 1 );
    return 0;
}